package search;

import java.util.ArrayList;

/**
 * 二分查找的前提是该数组是有序的
 */
public class BinatySearch {
    public static void main(String[] args) {

//        int[] arr = {1,2,22,3,3,4,5,2,2,2,2,2,2,3,4,32,2,2,2,2,3};
        int[] arr = new int[100];
        for (int i = 0; i <100 ; i++) {
            arr[i] = i;
        }
        ArrayList<Integer> integers = binarySearch2(arr, 0, arr.length - 1, 2);
        System.out.println(integers);
    }

    //二分查找

    /**
     *
     * @param arr 待查找的数组
     * @param left  左边的索引
     * @param right
     * @param findVal 待查找的值
     * @return  返回查找的值的下标
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {

        //当left>right时，表示找完了都还没找到
        if(left>right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (findVal > midVal) {  //向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { //向右递归
            return binarySearch(arr, left, mid - 1, findVal);
        }else{
            return mid;
        }
    }


    //能够返回相同数据的索引集合
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {

        System.out.println("lllllllll");
        //当left>right时，表示找完了都还没找到
        if(left>right){
            return new ArrayList<Integer>();
        }
//        int mid = (left + right) / 2;
        int mid = left +(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal = arr[mid];

        if (findVal > midVal) {  //向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { //向左递归
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {

            ArrayList<Integer> resIndexlist = new ArrayList<Integer>();

            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                //否则就把temp放入集合中
                resIndexlist.add(temp);
                temp -= 1;
            }
            resIndexlist.add(mid);  //把中间的那个数放入

            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                }
                resIndexlist.add(temp);
                temp += 1;
            }
            return resIndexlist;

        }
    }

}
